package leetcode_acm.backtrack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月22日 21:48
 */
public class CombinationSum {
    private List<List<Integer>> list ;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        list = new LinkedList<>();
        //对nums做一个排序
        Arrays.sort(candidates);
        backtrack(candidates,0,target,new LinkedList<>());
        return list;
    }
    private void backtrack(int[] nums,int index,int sum,LinkedList<Integer> path){
        if(sum == 0){
            list.add(new LinkedList<>(path));
            return ;
        }
        for(int i = index;i < nums.length; i++){
            if(sum - nums[i] < 0){
                return;
            }
            //做出选择
            path.add(nums[i]);
            //递归回溯
            backtrack(nums,index,sum - nums[i],path);
            path.removeLast();
        }
    }
}
